/**************************************************************************************
* GameMap.java
* 
*************************************************************************************/
package creid.mythos.engine;

import java.io.Serializable;
import java.util.Iterator;
import java.util.LinkedList;

import creid.mythos.shared.SpriteMap;
import creid.mythos.ui.ColorData;

public class GameMap implements SpriteMap, Serializable
{
	//Constants/////////////////////////////////////////////////////////////////////////

	private static final long serialVersionUID = 8739425620565724840L;
	public static final int RANDOM_LOCATION = -99;
	public static final int MAX_ATTEMPTS = 200; //max random placement attempts

	public static final int VIEW_DISTANCE = 10; 

	//Layout types
	static final int LAYOUT_DUNGEON = 0;
	static final int LAYOUT_TOWN = 1;
	static final int LAYOUT_CAVE = 2;
		
	//Terrain markers
	static final int BOUNDARY = 0;
	static final int FILLER = 1;
	static final int ROOM_BORDER = 2;
	static final int ROOM_FLOOR = 3;
	static final int CORRIDOR = 4;
	static final int INTERSECTION = 5;
	static final int ROOM_CORNER = 6;
	static final int CLEAR_INTERSECTION = 7;
	
	//Room constraints
	public static final int MIN_ROOMS = 8;
	public static final int MAX_ROOMS = 25;
	public static final int MIN_ROOM_WIDTH = 4;
	public static final int MAX_ROOM_WIDTH = MAP_WIDTH/4;
	public static final int MAX_ROOM_HEIGHT = MAP_HEIGHT/4;
	public static final int MIN_ROOM_HEIGHT = 4;
	
	//tunnel digging codes
	public static final int UNDIGGABLE_GRID = -1;
	public static final int OK_GRID = 0;
	public static final int SAVE_POINT = 1;

	public static final int X = 0;
	public static final int Y = 1;

	public static final int NO_TARGET = -1;
	
    //Connectedness checking
    public static final boolean UNFILLED_FLOOR = false;
    public static final boolean FILLED_FLOOR = true;
    public static final int DIG_FAILED = -1;
    public static final boolean SOLID = true;

	//Dijkstra Mapping constants
	public static final int UNSET = 9999; //max values for Djikstra maps
	public static final int ORTH_DIST = 2; //orthogonal Dmap increase
	public static final int DIAG_DIST = 3; //diagonal Dmap increase
	public static final int OCCUPANT_PENALTY = 5;//10;//3; //diagonal Dmap increase
	public static final int MOB_PATH = 0;	//Map to the PCs for land mobs
	public static final int SMART_MOB_PATH = 2;	//Map to the PCs for land mobs
	public static final int ALLY_PATH = 1;	//Map to the mobs for land PCs
	public static final int SMART_ALLY_PATH = 3;	//Map to the mobs for land PCs
	public static final int PC_PATH = 4;	//Map to the PC, used by Pets to find the player
	public static final int DMAP_ARRAY_SIZE = 5;	
	//TODO: Possibly add maps for tunnelling creatures, for aquatic/amphibious, for flying, etc
	
	public static final int MIN_MOBS = 10;
	public static final int MAX_MOBS = 20;
	
	public static final int MIN_TREASURE = 2;
	public static final int MAX_TREASURE = 10;
	
	public static final int MAX_ACTOR_DISTANCE = SpriteMap.MAP_HEIGHT * SpriteMap.MAP_WIDTH;
	
	//Max tries for random generation / placement
	public static final int MAX_TRIES = 500;
	
	public static final int NO_HIGHLIGHT = -1;
	
	//Attributes////////////////////////////////////////////////////////////////////////

	//Type of map
	private int mapType;
	
	//challenge level of map
	private int level;
	
	//Tiles
	private Cell[][] map;
	
	//Exits
	private Exit[] exits;
	
	//Terrain types
	private int[] terrain;
	
	//Allies and mobs
	private LinkedList<Actor> pcs;
	private LinkedList<Actor> mobs;
	
	//Projections to run
	private LinkedList<Projection> projections;
	
	//Target mob
	private Actor target;

	//Special tiles
	private int[] mapSpecials;
	
	//List of monsters following player onto next level
	private LinkedList<Actor> followQueue;
	
	//Cell to highlight when looking around
	private int hx;
	private int hy;
	
	//Constructors//////////////////////////////////////////////////////////////////////

	public GameMap(int layout, int[] terrain, int level, Exit[] exits, int[] mapSpecials)
	{
		this.level = level;
		this.mapType = layout;
		this.setTerrain(terrain); 
		pcs = new LinkedList<Actor>();
		mobs = new LinkedList<Actor>();
		target = null;
		this.exits = exits;
		for (int i = 0; i < exits.length; i++)
			exits[i].setMap(this);
		
		this.mapSpecials = mapSpecials;
		followQueue = new LinkedList<Actor>();
		projections = new LinkedList<Projection>();
		
		hx = NO_HIGHLIGHT;
		hy = NO_HIGHLIGHT;
	}

	//Methods///////////////////////////////////////////////////////////////////////////

	Exit getExit(int index)
	{
		return exits[index];
	}
	
	boolean isGenerated()
	{
		if (map == null)
			return false;
		else 
			return true;
	}
	
	Cell getLocation(int x, int y)
	{
		if (x < 0 || x >= map.length || y < 0 || y >= map[0].length)
			return null;
		
		return map[x][y];
	}
	
	Cell getRelativeLocation(Cell start, int dx, int dy)
	{
		return map[start.getX() + dx][start.getY() + dy];
	}
	
	/**
	 * getSprite(x, y)
	 * return the sprite to draw
	 */
	@Override
	public char[] getSprite(int x, int y)
	{
		return map[x][y].getSprite();
	}

	/**
	 * generate: create the layout and add items, features and monsters 
	 */
	void generate()
	{
		//First, design the layout
		//map = MapData.generateMap(this, mapType);
		generateMapLayout();
		
		//Add required exits
		for (int e = 0; e < exits.length; e++)
			placeSpecialTerrain(exits[e]);
			//setLocation(exits[e], RANDOM_LOCATION, RANDOM_LOCATION);
		
		//Add monsters
		generateEncounters();

		//Add features
		
		//Add items
		generateTreasure();
	}
	
	/**
	 * 
	 */
	void placeFollowers()
	{
		if (followQueue == null || followQueue.isEmpty())
			return;
		
		//Check adjacent cells, starting from a random corner.
		int ax = Mythos.callRNG(1);
		int ay = Mythos.callRNG(1);
		int oldAY = ay;
		
		if (ax == 0)
			ax = -1;
		if (ay == 0)
			ay = -1;
		
		int dx = ax * -1;
		int dy = ay * -1;
		int sx = 2 * dx;
		int sy = 2 * dy;
		
		//Try to place followers in adjacent cells
		for (; ax != sx; ax += dx)
		{
			if (followQueue.isEmpty()) break;
			
			for (ay = oldAY; ay != sy; ay += dy)
			{
				if (followQueue.isEmpty()) break;
				
				System.out.println(ax + ", " + ay);
				Cell check = getRelativeLocation(followQueue.getFirst().getLocation(), ax, ay);
				if (check.canOccupy(followQueue.getFirst()))
				{
					//Move them to the follow queue
					placeActor(followQueue.removeFirst(), check.getX(), check.getY());
				}
			}
		}
	}
	
	/**
	 * Try to place an item at a given location. If we cannot place it there, try to place it nearby,
	 * favoring closer spaces. Fail if nowhere for it to go.
	 * TODO: If nearby area is full, get all items already occupying the space and find the worst one,
	 * if the new item is better than it, replace it and discard the worse.
	 * @param i: item to place
	 * @param x: coordinates
	 * @param y: coordinates
	 * @param inLOS: only check cells in LOS of original cell
	 * @return success
	 */
	boolean placeItem(Item i, int x, int y, boolean inLOS)
	{
		//Fail if occupied
		if(map[x][y].canHoldTreasure())
		{
			map[x][y].setTreasure(i);
			return true;
		}
		else //Try to place in a nearby location
		{
			LinkedList<Cell> picks = new LinkedList<Cell>();
			
			//Add all adjacent cells
			for (int dx = -1; dx < 2; dx++)
				for (int dy = -1; dy < 2; dy++)
				{
					if (dx == 0 && dy == 0)
						continue;
					picks.add(map[x+dx][y+dy]);
				}
			
			//Pull the cells out at random and try to place the items
			while (!picks.isEmpty())
			{
				int index = Mythos.callRNG(picks.size() - 1);
				Cell pick = picks.remove(index);
				
				if (pick.canHoldTreasure())
				{
					pick.setTreasure(i);
					return true;
				}
			}
			
			//If we didn't find an adjacent place to drop it, try one further away
			int minX = Math.max(x - 2, 1);
			int minY = Math.max(y - 2, 1);
			int maxX = Math.min(x+2, map.length - 2);
			int maxY = Math.min(y+2, map[0].length - 2);
			
			for (int dx = minX; dx <= maxX; dx++)
			{
				for (int dy = minY; dy <= maxY; dy++)
				{
					//Skip things that are too close
					if (Math.max(Math.abs(dx-x), Math.abs(dy-y)) < 2)
						continue;
					
					//If restricted to drop in LOS (LOF really) then don't accept cells on other side of wall or door
					//TODO: replace with check line of Fire
					if(inLOS && !checkLOS(map[x][y], map[dx][dy], 3, false))
						continue;
					
					picks.add(map[dx][dy]);
				}
			}
			
			while (!picks.isEmpty())
			{
				int index = Mythos.callRNG(picks.size() - 1);
				Cell pick = picks.remove(index);
				
				if (pick.canHoldTreasure())
				{
					pick.setTreasure(i);
					return true;
				}
			}
		}
		
		//We couldn't place it
		return false;
	}
	
	/**
	 * placePlayer: put the player on this map
	 */
	boolean placeActor(Actor a, int x, int y)
	{
		//Fail if occupied
		if (map[x][y].canOccupy(a))
		{
			map[x][y].setOccupant(a);
			a.setLocation(map[x][y]);
			
			if (a.getFaction() == Actor.PLAYER_FACTION)
				pcs.add(a);
			else
				mobs.add(a);
			return true;
		}
		
		return false;
	}
	
	boolean placeActor(Actor a)
	{
		int x = -1;
		int y = -1;
		
		for (int i = 0; i < MAX_ATTEMPTS; i++)
		{
			x = 1 + Mythos.callRNG(MAP_WIDTH - 2);
			y = 1 + Mythos.callRNG(MAP_HEIGHT - 2);
			
			//DOn't randomly place guys in reserved locations
			if (map[x][y].isReserved())
				continue;
			
			if (placeActor(a, x, y))
				return true;
		}
		
		return false;
	}
	
	Actor removeActor(Actor ex)
	{
		if (ex == null)
			return null;
		
		//Un-set target if target is removed
		if (target == ex)
		{
			target = null;
		}
		
		//LinkedList<Actor> actors = null;
		Iterator<Actor> actors = null;
		
		if (ex.getFaction() == Actor.PLAYER_FACTION)
			actors = pcs.iterator();
		else 
			actors = mobs.iterator();
		
		//Sanity check
		if (actors == null)
			return null;
		
		while(actors.hasNext())
		{
			Actor temp = actors.next();
			
			if (temp == ex)
			{
				actors.remove();
				
				//Take from their place on the map
				temp.getLocation().setOccupant(null);
				temp.setLocation(null);
				
				return temp;
			}
		}
		
		//We didn't find the actor for some reason
		return null;
	}

	public LinkedList<Actor> getFollowQueue()
	{
		return followQueue;
	}
	
	LinkedList<Actor> getPcs()
	{
		return pcs;
	}

	LinkedList<Actor> getMobs()
	{
		return mobs;
	}

	//Get the cell to move to for the player's path
	
	/**
	 * pathNext
	 * Determine what cell creature should move to next.
	 * @param myFaction
	 * @param pathType
	 * @param start
	 * @param fleeing
	 * @return
	 */
	Cell getPath(int myFaction, int pathType, Cell start, boolean fleeing)
	{
		//Default to standing still
		Cell path = start;
		
		for (int x = -1; x < 2; x++)
			for (int y = -1; y < 2; y++)
			{
				if (x == 0 && y == 0)
					continue;
				
				Cell check = getRelativeLocation(start, x, y);

				//Skip unusable squares
				if (check.getDMap(pathType) == GameMap.UNSET)
					continue;
				
				//Get distance of current target, adjusting for being occupied as long
				//as we are not talking about our own cell.
				int myCost = path.getDMap(pathType);
				int distance = check.getDMap(pathType);
								
				//Choose the adjacent cell that is closest to the player / an ally (farthest if fleeing)
				if (fleeing && (myCost < distance || (myCost == distance && Mythos.callRNG(1) == 0)))
					path = check;
				else if (myCost > distance || (myCost == distance && Mythos.callRNG(1) == 0))
					path = check;
			}
		return path;
	}
	
	/**
	 * updatePMap: calculate paths to player and allies
	 */
	void updateDMap(int whichMap)
	{
		//QUeue to hold cells to map
		LinkedList<Cell> qq = new LinkedList<Cell>();
		
		//Flood-fill the map with max distance
		for (int x = 0; x < SpriteMap.MAP_WIDTH; x++)
		{
			for (int y = 0; y < SpriteMap.MAP_HEIGHT; y++)
			{
				switch(whichMap)
				{
				case SMART_ALLY_PATH:
				case SMART_MOB_PATH:
				case PC_PATH:
					//TODO: This condition will need to vary based on pather's mobility type (aquatic, flying, kill-wall)
					if (map[x][y].isPassable() || map[x][y].isOperable())
					{
						map[x][y].setDMapped(false);
						map[x][y].setDMap(whichMap, UNSET);
					}
					else
						map[x][y].setDMapped(true);
					break;
					
				case ALLY_PATH:
				case MOB_PATH:
					//TODO: This condition will need to vary based on pather's mobility type (aquatic, flying, kill-wall)
					if (map[x][y].isPassable())
					{
						map[x][y].setDMapped(false);
						map[x][y].setDMap(whichMap, UNSET);
					}
					else
						map[x][y].setDMapped(true);
					break;
				}
			}
		}
		
		//Get the cells adjacent to allies
		
		LinkedList<Actor> targets;
		LinkedList<Actor> allies;

		switch(whichMap)
		{
		//This just paths to the player, ignoring other allies, and is used when allies want to go to the player
		case PC_PATH:
			targets = new LinkedList<Actor>();
			allies = new LinkedList<Actor>();
			for (Actor p: pcs)
				if (p instanceof Player)
				{
					targets.add(p);
					break;
				}
				else allies.add(p);
			
			for (Actor m: mobs)
				allies.add(m);
			break;

		case SMART_ALLY_PATH:
		case ALLY_PATH:
			targets = mobs;
			allies = pcs;
			break;
			
		//Default to MOB_PATH
		case SMART_MOB_PATH:
		case MOB_PATH:
		default:
			targets = pcs;
			allies = mobs;
		}
		
		for (Actor actor: targets)
		{
			actor.getLocation().setDMap(whichMap, 0);
			actor.getLocation().setDMapped(true);
			
			//Add adjacent cells to the to-check list
			//Add adjacent cells to queue
			for (int dx = -1; dx < 2; dx++)
			{
				for(int dy = -1; dy < 2; dy++)
				{
					if (dx == 0 && dy == 0)
						continue;
					
					Cell cell = map[actor.getLocation().getX() + dx][actor.getLocation().getY() + dy];
					if (!cell.isDMapped())
						qq.add(cell);
				}
			}
		}
		
		//Now process each cell in the queue, add its unchecked neighbors, and continue until all connected
		//Note that we should NEVER get an edge cell, these should ALWAYS be permawalls, even if made to not look like it.
		while (!qq.isEmpty())
		{
			Cell c = qq.poll();
			
			//Check our neighbors
			for (int x = -1; x < 2; x++)
			{
				for(int y = -1; y < 2; y++)
				{
					int distance = DIAG_DIST;
					
					//Don't count ourselves
					if (x == 0 && y == 0)
						continue;
					
					if (x == 0 || y == 0)
						distance = ORTH_DIST;
					
					Cell neighbor = map[c.getX() + x][c.getY() + y];
					
					if (!neighbor.isPassable() && neighbor.getOperation() == Cell.NO_OP)
						continue;
					
					distance += neighbor.getDMap(whichMap); //we are distance + neighbor distance
					
					//Update our distance if there is a better path (lower distance)
					if (c.getDMap(whichMap) > distance)
						c.setDMap(whichMap, distance);
					
					//Add our neighbor to be checked if it has not been already
					if (!neighbor.isDMapped())
					{
						neighbor.setDMapped(true);
						qq.add(neighbor);
					}
				}
			}
		}
		
		//Finally, add a penalty to all cells occupied by our allies
		for (Actor a: allies)
		{
			a.getLocation().setDMap(whichMap, a.getLocation().getDMap(whichMap) + OCCUPANT_PENALTY);
		}
	}

	public int[] getTerrain()
	{
		return terrain;
	}

	public void setTerrain(int[] terrain)
	{
		this.terrain = terrain;
	}
	
	public int getLevel()
	{
		return level;
	}

	public void setLevel(int level)
	{
		this.level = level;
	}

	@Override
	public int getPMap(int x, int y)
	{
		if (!map[x][y].isPassable())
			return 0;
		
		return map[x][y].getDMap(MOB_PATH);
	}	
	
	public boolean projectionsToRun()
	{
		if (projections.isEmpty())
			return false;
		else
			return true;
	}
	
	public Projection getNextProjection()
	{
		return projections.poll();
	}
	
	public void addProjection(Projection p)
	{
		projections.add(p);
	}
	
	/**
	 * calcDistance
	 * Calculate the square of the distance between A and B for comparison purposes
	 * With current map sizes max value is 4214, if map size were to grow massively
	 * this would need to be altered
	 * @param a First actor to be compared
	 * @param b Second actor to be compared
	 * @return
	 */
	int calcDistance(Actor a, Actor b)
	{
		int dx = Math.abs(b.getLocation().getX() - a.getLocation().getX());
		int dy = Math.abs(b.getLocation().getY() - a.getLocation().getY());
		return (int) Math.sqrt(dx*dx + dy*dy);
	}
	
	/**
	 * Returns the closest enemy Actor in sight
	 * @param a
	 * @return closest actor, or null if none in sight
	 */
	public Actor closestHostile(Actor a)
	{
		Actor hostile = null;
		int distance = VIEW_DISTANCE;
		
		LinkedList<Actor> hostiles;
		switch(a.getFaction())
		{
		case Actor.PLAYER_FACTION:
			hostiles = mobs;
			break;
		
		case Actor.MONSTER_FACTION:
		default:
			hostiles = pcs;
		}


		for(Actor h: hostiles)
		{
			if (!checkLOS(a.getLocation(), h.getLocation(), distance, false))
				continue;
			
			int d = calcDistance(a, h);
			if (d < distance || d == distance && Mythos.callRNG(1) > 0)
			{
				distance = d;
				hostile = h;
			}
		}
		
		return hostile;
	}
	
	@Override
	public int getTargetX()
	{
		if (target != null)
			return target.getLocation().getX();
		else
			return -99;
	}

	@Override
	public int getTargetY()
	{
		if (target != null)
			return target.getLocation().getY();
		else
			return -99;
	}
	
	public Actor nextTarget()
	{
		//Make sure there are mobs to target
		if (mobs == null || mobs.size() == 0)
		{
			target = null;
			return null;
		}

		//Otherwise, cycle through the list of mobs.
		int t = 0;
		if (target != null)

		{
			t = mobs.indexOf(target);
		}

		//Now cycle through the targets,looking for someone we can see
		boolean start = true;
		int end = t;
		while(start || t != end)
		{
			//A mob we can see
			if (!start && mobs.get(t).getLocation().isSeen())
			{
				target = mobs.get(t);
				break;
			}

			if (t == end)
				start = false;
			
			t++;
			//Loop
			if (t == mobs.size())
				t = 0;
		}

		return target;
	}
	
	/**
	 * Get the width in cells of the dungeon
	 * @return
	 */
	public int getWidth()
	{
		return map.length;
	}
	
	/**
	 * Get the height in cells of the dungeon
	 * @return
	 */
	public int getHeight()
	{
		return map[0].length;
	}
	
	/**
	 * placeSpecialTerrain
	 * @param special
	 * @return
	 */
	private boolean placeSpecialTerrain(Cell special)
	{
		for (int attempt = 0; attempt < MAX_TRIES; attempt++)
		{
			//Find a place that is not on the edge of the map
			int x = Mythos.callRNG(1, getWidth() - 1);
			int y = Mythos.callRNG(1, getHeight() - 1);

			if (map[x][y].isPassable())
			{
				map[x][y] = special;
				
				map[x][y].setMap(this);
				map[x][y].setX(x);
				map[x][y].setY(y);

				return true;
			}
		}
		
		return false;
	}
	
	//Map Generation Routines //////////////////////////////////////////////////////////////
	
    //-----------------------------------------------------------
    //floodFill
    // recursively flood a map
    //-----------------------------------------------------------
    
    void floodFill(boolean[][] map, int x, int y)
    {
            //fill the chosen spot
            map[x][y] = FILLED_FLOOR;
            
            //Now flood adjacent unfilled places in the 8 adjacent squares
            if (map[x-1][y-1] == UNFILLED_FLOOR)
                    floodFill(map, x-1, y-1);
            if (map[x][y-1] == UNFILLED_FLOOR)
                    floodFill(map, x, y-1);
            if (map[x+1][y-1] == UNFILLED_FLOOR)
                    floodFill(map, x+1, y-1);
            if (map[x+1][y] == UNFILLED_FLOOR)
                    floodFill(map, x+1, y);
            if (map[x+1][y+1] == UNFILLED_FLOOR)
                    floodFill(map, x+1, y+1);
            if (map[x][y+1] == UNFILLED_FLOOR)
                    floodFill(map, x, y+1);
            if (map[x-1][y+1] == UNFILLED_FLOOR)
                    floodFill(map, x-1, y+1);
            if (map[x-1][y] == UNFILLED_FLOOR)
                    floodFill(map, x-1, y);
    }
    
    //-----------------------------------------------------------
    //testConnectedness
    // check to see if the level is connected
    //-----------------------------------------------------------
    
    boolean testConnectedness(int[][] map, int startX, int startY)
    {
            //Create an int map to work with
            boolean[][] check = new boolean[map.length][map[0].length];

            for (int x = 0; x < map.length; x++)
            {
                    for (int y = 0; y < map[0].length; y++)
                    {
                            if (map[x][y] == ROOM_FLOOR || map[x][y] == CORRIDOR || map[x][y] == INTERSECTION)
                                    check[x][y] = UNFILLED_FLOOR;
                            else 
                                    check[x][y] = SOLID;
                    }
            }
            
            //Sanity check
            if (check[startX][startY] != UNFILLED_FLOOR)
            {
                    Mythos.logger.errorLog("testConnectedness: Attempt to flood-fill with invalid starting point (" + startX + "," + startY + "), terrain=" + map[startX][startY]);
                    return false; //to avoid infinite loops
            }
            
            //And try to fill the dungeon to check for connectedness
            floodFill(check, startX, startY);
            
            //Now check to see if the whole map is connected
            boolean connected = true;
            for (int x = 0; x < check.length; x++)
                    for (int y = 0; y < check[0].length; y++)
                            if (check[x][y] == UNFILLED_FLOOR)
                            {
                                    connected = false;
                                    //map[x][y] = WALL;
                            }
            
            //Else map is wholly connected
            return connected;
    }
	
	/**
	 * 
	 * @param map
	 * @param placeR
	 * @param placeC
	 * @param xSize
	 * @param ySize
	 * @return
	 */
	boolean makeRoom(int[][] map, int placeR, int placeC, int xSize, int ySize)
	{
		//top and bottom sides
		for (int i = placeR; i <= placeR + xSize; i++)
			if (map[i][placeC] != FILLER || map[i][placeC + ySize] != FILLER)
			{
				return false;
			}
		
		//left and right sides
		for (int i = placeC; i <= placeC + ySize; i++)
			if (map[placeR][i] != FILLER || map[placeR + xSize][i] != FILLER)
			{
				return false;
			}
		
		//We are OK, create the room
		for (int x = placeR; x < placeR+xSize; x++)
		{
			for (int y = placeC; y < placeC+ySize; y++)
			{
				//Room boundaries
				if (x == placeR || x+1 == placeR+xSize)
				{
					if (y == placeC || y+1 == placeC+ySize)
						map[x][y] = ROOM_CORNER;
					else
						map[x][y] = ROOM_BORDER;
				}
				else if (y == placeR || y+1 == placeC+ySize)
				{
					map[x][y] = ROOM_BORDER;
				}
				//Room middle
				else
				{
					map[x][y] = ROOM_FLOOR;
				}
			}
		}
		
		//room can be placed here
		return true;
	}
	
	/**
	 * unDigSquare
	 * @param map
	 * @param x
	 * @param y
	 * @return Whether we stopped because we entered a room and don't need to continue
	 */
	boolean unDigSquare(int[][] map, int x, int y)
	{
		switch(map[x][y])
		{
			case CORRIDOR:
				map[x][y] = FILLER;
				break;
			case INTERSECTION:
				map[x][y] = ROOM_BORDER;
				break;
			case ROOM_FLOOR:
				return true;
		}
		
		return false;
	}
	
	/**
	 * digSquare
	 * @param map
	 * @param x
	 * @param y
	 * @param nextX
	 * @param nextY
	 * @return
	 */
	
	boolean digSquare(int[][] map, int x, int y, int nextX, int nextY)
	{
		//Check for terrain types we can never dig through
		if (map[x][y] == ROOM_CORNER || map[x][y] == BOUNDARY)
		{
			//We cannot continue
			return false;
		}
		
		//Dig the square
		if (map[x][y] == FILLER)
			map[x][y] = CORRIDOR;
		else if (map[x][y] == ROOM_BORDER)
			map[x][y] = INTERSECTION;
					
		return true;
	}
	
	/**
	 * tunnelVertically
	 * @param map
	 * @param xPos
	 * @param startY
	 * @param endY
	 * @return
	 */
	
	int tunnelVertically(int[][] map, int xPos, int startY, int endY)
	{
		int y = startY;
		//int saveY = startY;
		
		boolean make = true;
				
		//Direction we are moving
		int dy = 1;
		if (startY > endY)
			dy = -1;
		
		do
		{
			y += dy;
			
			int nextY = y + dy;
			//bounds check
			if (y == endY)
				nextY = y;

			make = digSquare(map, xPos, y, xPos, nextY);
		} while (y != endY && make);
		
		//undo our tunnel if needed (i.e. we ran into a room corner
		if (!make)
		{
			if (y - dy != startY)
			{
				while(y != startY)
				{
					//Current position was not change, so move first
					y -= dy;
					
					if (y == startY)
						break;
					
					//Undig until we get to a room
					if(unDigSquare(map, xPos, y))
						break;
				}
			}
			
			y = DIG_FAILED;
		}
		
		return y;
	}
	
	/**
	 * tunnelHorizontally
	 * @param map
	 * @param startX
	 * @param endX
	 * @param yPos
	 * @return
	 */
	
	int tunnelHorizontally(int[][] map, int startX, int endX, int yPos)
	{
		int x = startX;
		boolean make = true;
				
		//Direction we are moving
		int dx = 1;
		if (startX > endX)
			dx = -1;
		
		do
		{
			x += dx;
			
			int nextX = x + dx;
			//bounds check
			if (x == endX)
				nextX = x;

			//dig the square and handle the results
			make = digSquare(map, x, yPos, nextX, yPos);
		} while (x != endX && make);
		
		//undo our tunnel if needed (i.e. we ran into a room corner
		if (!make)
		{
			if (x - dx != startX)
			{
				while(x != startX)
				{
					//Current position was not change, so move first
					x -= dx;
					
					if (x == startX)
						break;
					
					//Undig until we get to a room
					if(unDigSquare(map, x, yPos))
						break;
				}
			}
			
			x = DIG_FAILED;
		}
		
		return x;
	} 
	
	/**
	 * makeTunnel
	 * @param map
	 * @param sx
	 * @param sy
	 * @param dx
	 * @param dy
	 * @return
	 */
	
	public boolean makeTunnel (int[][] map, int sx, int sy, int dx, int dy)
	{
		if (Math.abs(dx - sx) > Math.abs(dy - sy))
		{
			//First make the longer tunnel
			int endX = tunnelHorizontally(map, sx, dx, sy);
			
			//If we could not reach another room, fail
			if (endX == -1)
				return false;
			
			//else make the second part of the tunnel
			if (tunnelVertically(map, endX, sy, dy) == DIG_FAILED)
			{
				int x = endX;
				int change = 1;
				if (dx < sx)
					change = -1;
				
				while(x != sx)
				{
					//Current position was not change, so move first
					x -= change;
					
					//Undig until we get to a room
					if(unDigSquare(map, x, sy))
						break;
				}
			}
		}
		else
		{
			//First make the longer tunnel
			int endY = tunnelVertically(map, sx, sy, dy);
			
			//If we could not reach another room, fail
			if (endY == -1)
				return false;
			
			//else make the second part of the tunnel
			if (tunnelHorizontally(map, sx, dx, endY) == DIG_FAILED)
			{
				int y = endY;
				
				int change = 1;
				if (dy < sy)
					change = -1;
				
				while(y != sy)
				{
					//Current position was not change, so move first
					y -= change;
					
					//Undig until we get to a room
					if(unDigSquare(map, sx, y))
						break;
				}
			}
		}
		
		return true;
	}
	
	/**
	 * connect rooms with corridors
	 * @param map
	 * @param numRooms
	 * @param roomCorner
	 * @param roomSize
	 * @param onlyUnconnected
	 */
	
	void connectRooms(int[][] map, int numRooms, int[][] roomCorner, int[][] roomSize, boolean onlyUnconnected)
	{
		for (int i = 0; i < numRooms; i++)
		{
			//Pick a room to connect to
			int destRoom = Mythos.callRNG(0, numRooms - 1);
			
			//Don't make a tunnel to ourselves
			if (destRoom == i) continue;
						
			//Pick start and destination coords for hall (start in one room and end in another
			int startX = Mythos.callRNG(1, roomSize[i][X] - 1) + roomCorner[i][X];
			int startY = Mythos.callRNG(1, roomSize[i][Y] - 1) + roomCorner[i][Y];
			
			int endX = Mythos.callRNG(1, roomSize[destRoom][X] - 1) + roomCorner[destRoom][X];
			int endY = Mythos.callRNG(1, roomSize[destRoom][Y] - 1) + roomCorner[destRoom][Y];
			
			//Only increment counter if we actually created a tunnel somewhere
			if(!makeTunnel(map, startX, startY, endX, endY))
				i--;
		}
	}
	
	private int[][] generateDungeonLayout()
	{
		//Play with an integer representation of the map
		int[][] layout = new int[SpriteMap.MAP_WIDTH][SpriteMap.MAP_HEIGHT];

		//Second, create the canvas of terrain on which we will carve out a map
		int createAttempts = 0;
		int fillX = 0;
		int fillY = 0;
		
		do
		{
			//TODO: Pull the filler and special room placement out of the generation routine,
			//Change the loop to be in generateLayout and have generateDungeonLayout return null if not connected
			//Fill with filler terrain, bounded by perma-walls
			for (int x = 0; x < MAP_WIDTH; x++)
			{
				for (int y = 0; y < MAP_HEIGHT; y++)
				{
					//Boundaries fill with edge terrain
					if (x == 0 || y == 0 || x+1 == MAP_WIDTH || y+1 == MAP_HEIGHT)
						layout[x][y] = BOUNDARY;
					else
						layout[x][y] = FILLER;
				}
			}
			
			//Place any special room prototypes if we need to
			if (mapSpecials != null && mapSpecials.length > 0)
			{
				//Randomly place each item.
				for(int s = 0; s < mapSpecials.length; s++)
				{
					MapSpecial special = Mythos.MapSpecials[s];
					
					//Pick a location for the room
					int tries = 20;
					while (tries > 0)
					{
						tries--;
						
						//Choose a random placement
						int placeX = Mythos.callRNG(1, GameMap.MAP_WIDTH - 1 - special.getRoom().length);
						int placeY = Mythos.callRNG(1, GameMap.MAP_HEIGHT - 1 - special.getRoom()[0].length);
						
						//make sure we are not hitting anything
						boolean proceed = true;
						for (int cx = 0; cx < special.getRoom().length; cx++)
						{
							for (int cy = 0; cy < special.getRoom()[0].length; cy++)
							{
								if (layout[placeX+cx][placeY+cy] != FILLER)
								{
									proceed = false;
									break;
								}
							}
							
							if (!proceed) break;
						}
						
						if (proceed)
						{
							//Save location
							special.setRoomX(placeX);
							special.setRoomY(placeY);
							
							for (int fx = 0; fx < special.getRoom().length; fx++)
							{
								for (int fy = 0; fy < special.getRoom()[0].length; fy++)
								{
									if (special.getRoom()[fx][fy] == MapSpecial.WALL_CHAR)
										layout[placeX+fx][placeY+fy] = BOUNDARY;
									else
										layout[placeX+fx][placeY+fy] = ROOM_FLOOR;
								}
							}
							
							//success
							break;
						}
					}
				}
			}
			
			//TODO: implement fixed and randomly assigend special rooms (i.e. vaults, pits, etc)
			
			
			//Now, create some rooms
			int max = MAX_ROOMS - 1;
			if (mapSpecials != null)
				max -= mapSpecials.length;
			
			int totalRooms = Mythos.callRNG(MIN_ROOMS, max); //reduce room requirements for number of special rooms
			int numRooms = 0;
			int roomAttempts = 0;
		
			//Room data
			int[][] roomCorner = new int[totalRooms][2];
			int[][] roomSize = new int[totalRooms][2];
			
			//place the rooms
			while (numRooms < totalRooms && roomAttempts < MAX_ATTEMPTS)
			{
				roomAttempts++;

				//Pick a size for the room
				int rxSize = Mythos.callRNG(MIN_ROOM_WIDTH, MAX_ROOM_WIDTH);
							
				int rySize = Mythos.callRNG(MIN_ROOM_HEIGHT, MAX_ROOM_HEIGHT);
				
				//Pick a starting x,y point
				int placeR = Mythos.callRNG(1, MAP_WIDTH - rxSize - 2);
		
				int placeC = Mythos.callRNG(1, MAP_HEIGHT - rySize - 2);
				
				
				//Boundary checking
				if (placeR + rxSize >= MAP_WIDTH - 1)
					rxSize = MAP_WIDTH - placeR - 2;
				if (placeC + rySize >= MAP_HEIGHT - 1)
					rySize = MAP_HEIGHT - placeC - 2;
				
				//Now that we know where and how big, try to add the room
				if(makeRoom(layout, placeR, placeC, rxSize, rySize))
				{
					roomCorner[numRooms][X] = placeR;
					roomCorner[numRooms][Y] = placeC;
					roomSize[numRooms][X] = rxSize;
					roomSize[numRooms][Y] = rySize;
					numRooms++;
				}
			}
			
			System.out.println(numRooms + " rooms in " + roomAttempts + " attempts\n");
		
			if (numRooms < MIN_ROOMS && roomAttempts >= MAX_ATTEMPTS)
			{
				//Mythos.logger.errorLog("GameMap.generateDungeonLayout(): failed to create rooms!");
				continue;
			}
			
			//Connect the rooms with hallways
			connectRooms(layout, numRooms, roomCorner, roomSize, false);
			
			fillX = roomCorner[0][X] + 1;
            fillY = roomCorner[0][Y] + 1;

		} while (!testConnectedness(layout, fillX, fillY) && createAttempts < MAX_ATTEMPTS);

		//remove lines of doors to make large openings more fun and look better
		for (int x = 1; x < MAP_WIDTH - 1; x++)
			for (int y = 1; y < MAP_HEIGHT - 1; y++)
			{
				if (layout[x][y] == INTERSECTION || layout[x][y] == CLEAR_INTERSECTION)
				{
					boolean remove = false;
					
					for (int i = -1; i < 2; i++)
						for (int j = -1; j < 2; j++)
						{
							if (remove && layout[x+i][y+j] == INTERSECTION)
							{
								layout[x+i][y+j] = CLEAR_INTERSECTION;
							}
							else if ((i != 0 || j != 0) && layout[x+i][y+j] == INTERSECTION)
							{
								remove = true;
								i = -1;
								j = -1;
							}
						}
				}
			}
		
		//Now go clean up the tiles
		for (int x = 0; x < MAP_WIDTH; x++)
			for (int y = 0; y < MAP_HEIGHT; y++)
			{					
				//Clean up the 'break' tiles
				if (layout[x][y] == ROOM_CORNER) 
					layout[x][y] = ROOM_BORDER;
				//Sometimes don't make doors
				else if (layout[x][y] == INTERSECTION && Mythos.callRNG(1, 4) == 1)
					layout[x][y] = CORRIDOR;
				else if (layout[x][y] == CLEAR_INTERSECTION)
					layout[x][y] = CORRIDOR;
			}
		
		//we are (finally) done
		return layout;
	}
	
	private void generateMapLayout()
	{
		int[][] layout = null;
		switch(mapType)
		{
		case LAYOUT_DUNGEON:
			layout = generateDungeonLayout();
			break;
		default:
			Mythos.logger.errorLog("GameMap.generateMapLayout() called with unknown layout type '" + mapType + "'"); 	
			layout = generateDungeonLayout();
		}
		
		//From the layout, create the cells
		map = new Cell[MAP_WIDTH][MAP_HEIGHT];
		
		//Fill in the correct terrain types
		for (int x = 0; x < map.length; x++)
			for (int y = 0; y < map[0].length; y++)
			{
				int tIndex = terrain[layout[x][y]];
				map[x][y] = new Cell(this, x, y, Mythos.TerrainTypes[tIndex]); //Too many square brackets!
			}
		
		//Fill in the special rooms with cool stuff
		if (mapSpecials != null)
			for (int i: mapSpecials)
			{
				MapSpecial ms = Mythos.MapSpecials[i];
				
				//Go through the room, changing terrain as needed
				for (int x = 0; x < ms.getRoom().length; x++)
				{
					for (int y = 0; y < ms.getRoom()[0].length; y++)
					{
						int mx = ms.getRoomX() + x;
						int my = ms.getRoomY() + y;
						
						map[ms.getRoomX() + x][ms.getRoomY() + y].setReserved(true);
						
						if (ms.getRoom()[x][y] == MapSpecial.FLOOR_CHAR)
						{
							continue;
						}

						else if (ms.getRoom()[x][y] == MapSpecial.WALL_CHAR)
						{

							map[mx][my].setTerrain(Mythos.TerrainTypes[terrain[BOUNDARY]]);
							continue;
						}
						else if (ms.getRoom()[x][y] == MapSpecial.DOOR_CHAR)
						{
							map[mx][my].setTerrain(Mythos.TerrainTypes[terrain[INTERSECTION]]);
							continue;
						}
						
						//Otherwise, get the special this matches
						char c= ms.getRoom()[x][y];
						String datum = ms.getSpecial(c);
						String[] data = datum.split(":");
						
						//Index 0 is Mob data
						int m = Integer.parseInt(data[0]);

						if (m != 0)
						{

							Actor mob = null;
							
							if (m >= 1) //specific mob to generate
							{
								mob = new Actor(Mythos.CreatureTypes[m]);
							}
							else //random mob, up to (-1*m - 1) levels deeper, so -1 translates to same depth
							{
								m *= -1;
								m--;
								mob = Mythos.randomMob(level + m);
							}
	
							placeActor(mob, mx, my);
						}
						
						//Index 1 is item data
						int o = Integer.parseInt(data[1]);
						if (o != 0)
						{
							Item thing = null;
							
							if (o > 0)
							{
								
							}
							else
							{
								
							}
							
							placeItem(thing, mx, my, false);
						}
						
						//Index 2 is terrain data
						int t = Integer.parseInt(data[2]);
						//don't allow random terrain. Not sure why it would be useful, wouldn't want to randomly generate a bunch of junk.
						if (t != 0)
						{
							map[mx][my].setTerrain(Mythos.TerrainTypes[t]);
						}
					}
				}
			}

	}
	
	//generate encounters
	private void generateEncounters() //TODO: Add monster ecologies to tailor mob population to towns, dungeons, wildernesses
	{
		int min = MIN_MOBS;	//To allow map properties to have more or less than the normal range of creatures
		int max = MAX_MOBS;
		
		int mobCount = Mythos.callRNG(min, max);
		if (Mythos.DEBUG_NO_MOB_GEN)
			mobCount = 0;
		
		while(mobCount > 0)
		{
			//Randomly pick 2, take the higher-level one
			if(placeActor(Mythos.randomMob(level)))
				mobCount--;
		}
		
		//Add in an ally mob on the first level
		if (level == 1)
			placeActor(new Actor(Mythos.CreatureTypes[0]));
	}
	
	private void generateTreasure()
	{
		int amount = Mythos.callRNG(MIN_TREASURE, MAX_TREASURE);
		
		int attempts = 0;
		while (amount > 0 && attempts < MAX_ATTEMPTS)
		{
			int x = Mythos.callRNG(1, map.length - 2);
			int y = Mythos.callRNG(1, map[0].length - 2);
			
			if (map[x][y].canHoldTreasure())
			{
				map[x][y].setTreasure(Mythos.randomItem(level));
				amount--;
			}
			
			attempts++;
		}
	}
	
	@Override
	public String targetName()
	{
		String name = SpriteMap.NO_TARGET_NAME;
		if (target != null)
			name = target.getSingularName();
					
		return name;
	}

	@Override
	public String targetHealth()
	{
		String health = SpriteMap.NO_TARGET_HEALTH;
		if (target != null)
			health = "Health: " + target.getHealth() + "/" + target.getMaxHealth();
		
		return health;
	}

	@Override
	public char targetHealthColor()
	{
		if (target != null)
		{
			if (target.getHealth() * 3 <= target.getMaxHealth())
				return ColorData.RED;
			else if (target.getHealth() * 3 <= target.getMaxHealth() *2)
				return ColorData.YELLOW;
			else
				return ColorData.GREEN;
		}	
		else
			return ColorData.BLACK;
	}
	
	public boolean isSeen(int x, int y)
	{
		return map[x][y].isSeen();
	}
	
	//-----------------------------------------------------
	//checkLOS
	// trace a path from the viewer to the destination to
	// see if there is a valid LOS to it
	//-----------------------------------------------------

	public boolean checkLOS(Cell source, Cell destination, int viewDistance, boolean updateFOV)
	{
		//LinkedList<Cell> line = getLine(source, destination);
		//LinkedList<Cell> line = getLine(source, destination);
		Cell[] line = getLine(source, destination);
		
		//If the destination is too far away to see, we cannot see it
		if (line.length > viewDistance)
			return false;
		
		if (updateFOV)
			source.setSeen(true);
		
		boolean inLOS = false;
		
		//Go through the line of cells, marking as seen until we hit the end
		for (int i = 0; i < line.length; i++)
		//for (int i = 0; i < Math.min(viewDistance, line.size()); i++)
		{
			if (updateFOV)
				line[i].setSeen(true);
				//line.get(i).setSeen(true);
			
			//if (line.get(i) == destination)
			if (line[i] == destination)
				inLOS = true;
			
			//Stop if we can't see anything through this
			//if (line.get(i).isOpaque())
			if (line[i].isOpaque())
				break;
		}
		
		return inLOS;
	}
	
	//-----------------------------------------------------
	// updateLOS
	// fix square's inLOS flags after a player move
	//-----------------------------------------------------
	public void updateFOV(Cell viewPoint)
	{
		//TODO: Alter range by player's light level, and by the innate "darkness" of the map
		int maxDistance = VIEW_DISTANCE;
		
		//start with a blank slate
		for (int x = 0; x < getWidth(); x++)
			for (int y = 0; y < getHeight(); y++)
				getLocation(x, y).setSeen(false);
		
		viewPoint.setSeen(true);
		
		for (int x = 0; x < getWidth(); x++)
		{
			for (int y = 0; y < getHeight(); y++)
			{
				checkLOS(viewPoint, getLocation(x, y), maxDistance, true);
			}
		}
		
		//If the player's target is no longer in view, un-target
		if (target != null && !target.getLocation().isSeen())
			target = null;
		
		
	}

	/**
	 * getSymmetricLine: Provide an array of cells, for which getSymmetricLine(A, B) is equivalent to getSymmetricLine(B, A)
	 * @param start
	 * @param end
	 * @return
	 */
	
	public Cell[] getLine(Cell start, Cell end)
	{
		LinkedList<Cell> cells = new LinkedList<Cell>();
		
		//Easy case: same cell
		if (start.getX() == end.getX() && start.getY() == end.getY())
		{
			return new Cell[]{start};
		}

		//Easy case: horizontal line
		if (start.getX() == end.getX())
		{
			int y = start.getY();
			int dy = 1;
			if (end.getY() < start.getY())
				dy = -1;
			
			while (y != end.getY())
			{
				cells.add(map[start.getX()][y]);
				y += dy;
			}
			cells.add(map[start.getX()][y]);
		}
		//Easy case: vertical line
		else if (start.getY() == end.getY())
		{
			int x = start.getX();
			int dx = 1;
			if (end.getX() < start.getX())
				dx = -1;
			
			while (x != end.getX())
			{
				cells.add(map[x][start.getY()]);
				x += dx;
			}
			cells.add(map[x][start.getY()]);
		}
		else
		{
			int sx = start.getX();
			int fx = end.getX();
			
			int sy = start.getY();
			int fy = end.getY();
			
			int dx = fx - sx;
			int dy = fy - sy;
	
			//Easy case: 45-degree angle
			if (Math.abs(dx) == Math.abs(dy))
			{
				int x = sx;
				int y = sy;
				
				int cx = 1;
				if (fx < sx)
					cx = -1;
				
				int cy = 1;
				if (fy < sy)
					cy = -1;
				
				while (x != fx)
				{
					cells.add(map[x][y]);
					x += cx;
					y += cy;
				}
				
				cells.add(end);
				
				return cells.toArray(new Cell[cells.size()]);
			}
			else
			{
				//Hard cases: Arbitrary line
				int cx = 1;
				if (dx < 0)
					cx = -1;
		
				int cy = 1;
				if (dy < 0)
					cy = -1;
		
				dx = Math.abs(dx);
				dy = Math.abs(dy);
		
				int err = dx-dy;
		
				int x = sx;
				int y = sy;
				
				while (true)
				{
					cells.add(map[x][y]);
					if (x == fx && y == fy)
						break;
					
					int e2 = 2*err;
					
					if (e2 > (dy * -1))
					{
						err = err - dy;
						x = x + cx;
					}
					
					if (e2 < dx)
					{
						err = err + dx;
						y = y + cy;
					}
				}
			}
		}
		
		return cells.toArray(new Cell[cells.size()]);
	}
	
	public void setTarget(Actor target)
	{
		//Don't target something that somehow isn't in our mobs list
		for(Actor a: mobs)
		{
			if (a == target)
				this.target = a;
		}
	}
	
	/**
	 * cleanUp: Heal mobs, put out fields, purge temp statuses, etc
	 */
	void cleanUp()
	{
		for (Actor m: mobs)
		{
			m.setHealth(m.getMaxHealth());
		}
	}
	
	public int getHighlightX()
	{
		return hx;
	}
	
	public int getHighlightY()
	{
		return hy;
	}
	
	void setHighlight(int x, int y)
	{
		hx = x;
		hy = y;
	}
	
	void changeHighlightX(int change)
	{
		hx += change;
		
		if (hx < 0)
			hx = 0;
		else if ( hx >= map.length)
			hx = map.length - 1;
	}
	
	void changeHighlightY(int change)
	{
		hy += change;
		if (hy < 0)
			hy = 0;
		else if ( hy >= map[0].length)
			hy = map[0].length - 1;
	}
	
	String getHighlightedCellName()
	{
		if (hx == NO_HIGHLIGHT || hy == NO_HIGHLIGHT)
			return "Nowhere";
		else	
			return map[hx][hy].getName(Entity.INDEFINITE);
	}
	
	void removeHighlight()
	{
		hx = hy = NO_HIGHLIGHT;
	}
	
	Actor getTarget()
	{
		return target;
	}
	
	/**
	 * findStartingLocation()
	 * Place player on upstairs of dungeon
	 * @return
	 */
	Cell findStartingLocation()
	{
		for(int x = 0; x < map.length; x++)
			for(int y = 0; y < map[0].length; y++)
				if (map[x][y].getTerrainType() == GameWorld.START_TERRAIN_TYPE)
					return map[x][y];
		
		//Should never get here
		return null;
	}
}